package com.yulongtian.weekCompetition.month202301.week03;

import java.util.HashMap;

/**
 * 可
 *
 * @author yulongTian
 * @create 2023-01-15 10:52
 */
public class Test03 {
    public static void main(String[] args) {
        System.out.println(countGood(new int[]{2, 1, 3, 1, 2, 2, 3, 3, 2, 2, 1, 1, 1, 3, 1}, 11));
//        System.out.println(countGood(new int[]{3, 1, 4, 3, 2, 2, 4}, 2));
    }

    public static long countGood(int[] nums, int k) {
        long ans = 0L;
        int left = 0;
        int checkNum = 0;
        int preN = 0;
        int nowN = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int right = 0; right < nums.length; right++) {
            if (!map.containsKey(nums[right])) {
                map.put(nums[right], 1);
                preN = 0;
                nowN = 1;
            } else {
                preN = map.get(nums[right]);
                nowN = preN + 1;
                map.put(nums[right], map.get(nums[right]) + 1);
            }
            if (preN != 0 && nowN > preN) {
                checkNum += preN;
            }
            while (checkNum >= k) {
                ans += nums.length - right;
                preN = map.get(nums[left]);
                nowN = preN - 1;
                map.put(nums[left], nowN);
                left++;
                checkNum -= preN - 1;
            }
        }
        return ans;
    }

}
